package com.li.sort.arithmetic;

import java.util.Random;

public class QuickSort {
	public static final int SIZE = 1000000;
	public static void main(String[] args) {
		int[] array = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			array[i] = random.nextInt(100);
		}
		int[] array2 = array.clone();
		
		//System.out.println(Arrays.toString(array));
		
		long time1= System.currentTimeMillis();
		System.out.println("##############################################");
		quickSort(array,0,array.length-1);
		//System.out.println(Arrays.toString(array));
		System.out.println(System.currentTimeMillis()-time1);
		
		long time2= System.currentTimeMillis();
		System.out.println("##############################################");
		quickSort2(array2,0,array2.length-1);
		//System.out.println(Arrays.toString(array2));
		System.out.println(System.currentTimeMillis()-time2);
	}
	
	
	public static void quickSort(int[] array, int low, int high) {  
        // 解决和合并  
        if (low <= high) {  
            int mid = partition(array, low, high);  
            // 递归  
            quickSort(array, low, mid - 1);
            quickSort(array, mid + 1, high);  
        }  
  
    }
	
	public static void quickSort2(int[] array, int lo,int hi) {  
		 if(lo>=hi){
	            return ;
	        }
	        int index=partition2(array,lo,hi);
	        quickSort2(array,lo,index-1);
	        quickSort2(array,index+1,hi); 
    }
	
	public static int partition2(int[] array,int lo,int hi) {  
		 //固定的切分方式
        int key=array[lo];
        while(lo<hi){
            while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
                hi--;
            }
            array[lo]=array[hi];
            while(array[lo]<=key&&hi>lo){
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
	}  
	/**
	 * n-1趟就ok
	 * @param array
	 */
	public static int partition(int[] array, int low, int high){
		 // 分解  
        int pivot = array[high];  
        int i = low - 1;  
        int temp;  
        for (int j = low; j < high; j++) {  
  
            if (array[j] < pivot) {  
                i++;  
                swap(array,i,j);   
            }  
        }  
        // 交换中间元素和privot  
        temp = array[i + 1];  
        array[i + 1] = array[high];  
        array[high] = temp;  
       // System.out.println(Arrays.toString(array));
        return i + 1;  
	}
	
	public static void swap(int[] array, int i, int j){  
	    int temp = array[i];  
	    array[i] = array[j];  
	    array[j] = temp;  
	}  
}
